\chapter{排列组合}

\section{组合数}
\begin{itemize}[leftmargin=\inteval{\myitemleftmargin}pt,itemsep=
   \inteval{\myitemitempsep}pt,topsep=\inteval{\myitemtopsep}pt]
   
\item \textbf{排列数}：
$ P_n^k=\dfrac{n!}{(n-k)!} $，或者写成$ A_n^k $. 

\item \textbf{组合数}：$ C_n^k=C_n^{n-k}=\dfrac{n!}{k!(n-k)!},\ 
C_n^k+C_n^{k-1}=C_{n+1}^k $.(\underline{上标取大，下标加1})

\item 因为阶乘函数增长太快，在大多数编程场景下，阶乘函数允许的自变量的范围很小，\\
$ 13! = 6227020800 >2^{32}-1 = 4294967295$ \ (32bit无符号整数的最大值)  \\
$ 21!\approx 5.109\times 10^{19} >2^{64}-1 \approx  1.845\times 10^{19}$ 
\ (64bit无符号整数的最大值)   \\
$ 35!\approx 1.033\times 10^{40} >2^{128} \approx  3.403\times 10^{38}$ 
\ (32bit浮点数的最大值)  \\
$ 171!\approx 1.241\times 10^{309} >2^{1024} \approx  1.798\times 10^{308}$ 
\ (64bit浮点数的最大值)  \\
所以，直接用数组(数列)存储阶乘的值，至多占用$ 171\times 8 = 1368 $\,Byte的存储空间(0到170，共171个)，就能满足64bit计算的需求。
不仅速度快，而且没有多次浮点乘法带来的累积误差
\footnote{阶乘的计算看起来全是整数的乘法，然而64bit的整数能表示的阶乘值
太小(最多到20!)，很多情况下不满足需求。如果不使用专门的计算巨大整数的工具，比如Maple, MPFR(Multiple-Precision Floating-point computations with correct Rounding), GMP(GNU Multiple Precision Arithmetic Library)，就必须把整数转化成浮点数进行
乘法运算，而浮点乘法是有误差的。上面说明把阶乘的值用数组进行存储，
这些用于存储的值就可以使用MPFR之类的工具进行计算。
计算巨大整数的工具本质上是使用了更多的bit数来存储整数，
而代价是计算耗时大大增加。}，是一般的编程场景下的最优方案。

\item 对于排列数$P_n^k$和组合数$C_n^k$，在编程计算的时候，
最好按$n$和$k$的大小分段实现：若$n<171$，则查询
存储阶乘值的数组，得到$n!$、$(n-k)! $、$ k!$，做一次除法得到$P_n^k$，
做一次乘法一次除法得到$C_n^k$；
若$n\geq 171$且$k$比较小(比如$k<30$)，
则直接用循环语句计算连乘积
$(n-k+1)(n-k+2)\cdots n$，这就是$P_n^k$，再查阶乘值数组得到$k!$，
计算$\dfrac{P_n^k}{k!}$即得$C_n^k$；
若$n\geq 171$且$k$比较大(比如$k\geq 30$)，那么连乘积的多次浮点乘法运算
会导致累积误差过大，所以就使用先求对数再求指数的方法，即
\begin{gather*}
    P_n^k=\exp{\left(\ln \dfrac{n!}{(n-k)!}\right)}=\exp{(\ln(n!)-\ln((n-k)!))} \\
    C_n^k=\exp{\left(\ln \dfrac{n!}{k!(n-k)!}\right)}=\exp{(\ln(n!)-\ln(k!)-\ln((n-k)!))}
\end{gather*}
其中$\exp()$表示以e为底的指数函数，阶乘的对数$\ln(n!)$则是
利用斯特林公式\eqref{斯特林公式对数形式2}进行计算
(也可以预先计算一部分数值后做成数组存储)，
不用担心因$n!$过大导致无法计算。
    
\item \textbf{二项式定理}：
\begin{gather}\label{二项式定理(a+b)^n展开}
    (a+b)^n=\sum\limits_{k=0}^nC_n^ka^kb^{n-k}=
    \sum\limits_{k=0}^nC_n^ka^{n-k}b^k
\end{gather}
\item 几个多项展开式：
\begin{align*}
    (a+b+c)^2 &=a^2+b^2+c^2+2(ab+ac+bc) \\
    (a+b+c)^3 &=a^3+b^3+c^3+3(a^2b+ab^2+b^2c+bc^2+a^2c+ac^2)+6abc \\
    (a+b+c)^4 &=a^4+b^4+c^4+4(a^3b+ab^3+b^3c+bc^3+a^3c+ac^3) \\
    &+6(a^2b^2+b^2c^2+a^2c^2)+12(a^2bc+ab^2c+abc^2) \\
    (a+b+c+d)^2 &=a^2+b^2+c^2+d^2+2(ab+ac+ad+bc+bd+cd) \\
    (a_1+a_2+\cdots+a_n)^2 &=a_1^2+a_2^2+\cdots+a_n^2+
    2\sum_{1\leq i<j\leq n}a_ia_j 
\end{align*}
\item \textbf{杨辉三角}：左右对称性($C_n^k=C_n^{n-k}$)，
内部元素等于肩上两数之和($C_n^k+C_n^{k-1}=C_{n+1}^k$)，
每行奇数项的和等于偶数项的和
($C_n^0+C_n^2+C_n^4+\cdots=C_n^1+C_n^3+C_n^4+\cdots$，
在\eqref{二项式定理(a+b)^n展开}式中令$a=1,\ b=-1$即可得到)，
第$2^n-1$行的每个数都是奇数(最上面的行定义为第0行，代表$(a+b)^0$)
\footnote{这个性质的一种证明方法要用到Lucas定理，参见
https://www.cut-the-knot.org/arithmetic/algebra/LucasTheorem.shtml}.
\begin{gather*}
    1 \\
    1\q 1 \\
    1\q 2 \q 1 \\   
    1\q 3 \q 3 \q 1 \\
    1\q 4 \q 6 \q 4 \q 1 \\
    1\q 5 \q 10 \q 10 \q 5 \q 1 \\
    1\q 6 \q 15 \q 20 \q 15 \q 6 \q 1  \\ 
    1\q 7 \q 21 \q 35 \q 35 \q 21 \q 7 \q 1  \\ 
    1\q 8 \q 28 \q 56 \q 70 \q 56 \q 28 \q 8 \q 1  \\ 
    1\q 9 \q 36 \q 84 \q 126 \q 126 \q 84 \q 36 \q 9 \q 1  \\ 
    1\q 10 \q 45 \q 120 \q 210 \q 252 \q 210 \q 120 \q 45 \q 10 \q 1  \\ 
    1\q 11 \q 55 \q 165 \q 330 \q 462 \q 462 \q 330 \q 165 \q 55 \q 11 \q 1 
\end{gather*}
设第$n$行的和为$S_n$，考虑$S_n$与$S_{n-1}$的关系。 $S_n-2$代表第$n$行排除掉
首尾的1之后所有元素的和(记为$T_n$，则$T_n=S_n-2$). 
如何由第$n-1$行得到$T_n$呢？
可以把第$n-1$行首尾的1使用一次、其余元素均使用2次，相加得到$T_n$.
即 $T_n=2+2(S_{n-1}-2)=2S_{n-1}-2$，于是$ S_n-2=2S_{n-1}-2 $，
$ S_n=2S_{n-1} $，根据$S_0=1$可得$S_n=2^n$. 
当然，在\eqref{二项式定理(a+b)^n展开}式中令
$a=b=1$也很容易得到$S_n=2^n$. 

感兴趣的读者可以研究杨辉三角每一行的最小公倍数。
杨辉三角还隐含了斐波那契数列。
\begin{align*}
    F_1=&\  C_0^0=1 \\
    F_2=&\  C_1^0=1 \\
    F_3=&\  C_2^0+C_1^1=2 \\
    F_4=&\  C_3^0+C_2^1=3 \\
    F_5=&\  C_4^0+C_3^1+C_2^2=5 \\
    F_6=&\  C_5^0+C_4^1+C_3^2=8 \\
    F_7=&\  C_6^0+C_5^1+C_4^2+C_3^3=13 \\
    F_8=&\  C_7^0+C_6^1+C_5^2+C_4^3=21 \\ 
    &\cdots \\
    F_n=&\  C_{n-1}^0+C_{n-2}^1+\cdots+C_{n-1-m}^m\quad \left(m=\left\lfloor
    \frac{n-1}{2} \right\rfloor\right)   
\end{align*}
其中，$ \lfloor x \rfloor $表示向下取整，即不超过$ x $的最大整数，比如
$ \lfloor 4.3 \rfloor=4,\ \lfloor 6.9 \rfloor=6 $. 

\item 莱布尼茨三角：最上面的行定义为第1行；第$n$行首尾的元素均为
$\dfrac{1}{n}$；内部元素等于其下方左右两元素之和；所有元素的分子都是1；
每行中间的元素小，两头的元素大；
\begin{gather*}
    \dfrac{1}{1} \\
    \dfrac{1}{2}\q \dfrac{1}{2} \\
    \dfrac{1}{3}\q \dfrac{1}{6} \q \dfrac{1}{3} \\   
    \dfrac{1}{4}\q \dfrac{1}{12} \q \dfrac{1}{12} \q \dfrac{1}{4} \\
    \dfrac{1}{5}\q \dfrac{1}{20} \q \dfrac{1}{30} \q \dfrac{1}{20} \q
    \dfrac{1}{5} \\
    \dfrac{1}{6}\q \dfrac{1}{30} \q \dfrac{1}{60} \q \dfrac{1}{60} \q
    \dfrac{1}{30}\q \dfrac{1}{6} \\
    \dfrac{1}{7}\q \dfrac{1}{42} \ \ \dfrac{1}{105} \ \ \dfrac{1}{140} \ \ 
    \dfrac{1}{105}\ \ \dfrac{1}{42}  \q \dfrac{1}{7}
\end{gather*}
第$n$行、$k(k\geq 1)$列的元素记为$L(n,k)$，
则$L(n,k)=\dfrac{1}{nC_{n-1}^{k-1}}=\dfrac{1}{kC_n^k}$. 
显然有
\begin{align*}
    L(n,k)+L(n,k+1)=&\ \dfrac{1}{nC_{n-1}^{k-1}}+
    \dfrac{1}{nC_{n-1}^{k}}=\dfrac{(k-1)!(n-k)!}{n\cdot(n-1)!}+
    \dfrac{k!(n-k-1)!}{n\cdot(n-1)!} \\
    =&\ \dfrac{(k-1)!(n-k-1)![(n-k)+k]}{n!}
    = \dfrac{(k-1)!(n-k-1)!}{(n-1)!} \\
    =&\ \dfrac{(k-1)![(n-2)-(k-1)]!}{(n-1)\cdot (n-2)!}=
    \dfrac{1}{(n-1)C_{n-2}^{k-1}}=L(n-1,k)
\end{align*}
设第$n$行的和为$S_n$，考虑$S_n$与$S_{n-1}$的关系。
可以把第$n$行首尾的$\dfrac{1}{n}$使用一次、其余元素均使用2次，
相加得到$S_{n-1}$. 即$S_{n-1}=2S_{n}-\dfrac{2}{n}$. 
两边同乘$2^{n-1}$，再移项，可得
\begin{gather*}
    2^{n}S_{n}=2^{n-1}S_{n-1}+\dfrac{2^{n}}{n}
\end{gather*}
累加后可得$ 2^{n}S_{n}=2S_{1}+\sum\limits_{k=2}^{n} \dfrac{2^{k}}{k}=
\sum\limits_{k=1}^{n} \dfrac{2^{k}}{k} $，两边除以$2^n$有
\begin{gather*}
    S_n=\dfrac{1}{2^n}\sum_{k=1}^{n} \dfrac{2^{k}}{k}
\end{gather*}
结合$L(n,k)$的表达式，又有如下等式：
\begin{gather*}
    S_n=\sum_{k=1}^{n}\dfrac{1}{nC_{n-1}^{k-1}}
    =\sum_{k=1}^{n}\dfrac{1}{kC_n^k}
    =\dfrac{1}{2^n}\sum_{k=1}^{n} \dfrac{2^{k}}{k}  \\
    \sum_{k=1}^{n}\dfrac{1}{C_{n-1}^{k-1}}=
    \dfrac{n}{2^n}\sum_{k=1}^{n} \dfrac{2^{k}}{k}
\end{gather*}

\item 加法原理(分类)，乘法原理(分步)。
\item 德摩根(De Morgan)定律：$ \overline{A \cap B}=\overline{A}\cup 
\overline{B},\ \overline{A \cup B}=\overline{A}\cap \overline{B} $. 
同一个等式中必定有一个交集符号，一个并集符号。

\item 含有$ n $个元素的集合的子集(包括空集和全集)的数量为
$ 2^n $，即$\sum\limits_{k=0}^{n} C_n^k=2^{n} $. 也可以认为每个元素都有
选出或不选出2种可能，
所以总共有$2\times 2\times \cdots\times 2= 2^n $种选法。

\item 求证：$ \sum\limits_{k=1}^{n} kC_n^k=n\cdot2^{n-1} $. \\
\textbf{方法一} 
\begin{gather*}
    kC_n^k=k\dfrac{n!}{k!(n-k)!}=n\dfrac{(n-1)!}{(k-1)![(n-1)-(k-1)]!}=nC_{n-1}^{k-1} 	
\end{gather*}
\begin{gather*}
    \sum_{k=1}^{n} kC_n^k=\sum_{k=1}^{n} nC_{n-1}^{k-1}=n\sum_{k=1}^{n} C_{n-1}^{k-1}
    =n\cdot 2^{n-1}
\end{gather*}
\textbf{方法二}
\begin{align*}
    (1+x)^n=C_n^0+C_n^1x+C_n^2x^2+\cdots + C_n^nx^n
\end{align*}
对$ x $求导：
\begin{align} \label{二项展开式两边求导}
    n(1+x)^{n-1}=C_n^1+2C_n^2x+\cdots + nC_n^nx^{n-1}
\end{align}
令$ x=1 $即可。\\
\textbf{方法三}\ 倒序相加：
\begin{align*}
    S_n=&\ 0C_n^0+C_n^1+2C_n^2+\cdots+(n-2)C_n^{n-2} +(n-1)C_n^{n-1}+ nC_n^n \\
    S_n=&\ nC_n^n+(n-1)C_n^{n-1}+(n-2)C_n^{n-2}+\cdots+2C_n^2+ C_n^1 +0C_n^0 \\
    2S_n=&\ n(C_n^0+C_n^1+\cdots +C_{n}^{n-1}+C_n^n)=n\cdot 2^n \\
    S_n=&\  n\cdot 2^{n-1}
\end{align*}

\item 一些组合恒等式：
\begin{table}[h] 
\caption{} 
\centering
\begin{tabular}{l|l} \label{组合恒等式}
    $\sum\limits_{k=r}^{n} C_k^r=C_{n+1}^{r+1}=C_n^r+C_n^{r+1}$  &		
    $\sum\limits_{k=0}^{r}C_m^kC_n^{r-k}=C_{m+n}^r $     \\
    $\sum\limits_{k=0}^{n} C_n^k=2^{n} $		&
    $\sum\limits_{k=1}^{n} kC_n^k=n\cdot2^{n-1} $  \\
    $\sum\limits_{k=1}^{n} k^2C_n^k=n(n+1)\cdot2^{n-2} $  &
    $\sum\limits_{k=0}^{n} C_{2n}^k=2^{2n-1}+\dfrac{(2n)!}{2(n!)^2} $  \\
    $\sum\limits_{k=0}^{n} \left( C_{n}^k\right) ^2=C_{2n}^n=\dfrac{(2n)!}{(n!)^2} $  &
    $C_n^kC_k^r=C_n^rC_{n-r}^{k-r} $
\end{tabular}
\end{table} 

\item 在等式$ (1+x)^n=C_n^0+C_n^1x+C_n^2x^2+\cdots + C_n^nx^n $
中令$ x=\i $\ (虚数单位)，则
\begin{align*}
    (1+\i)^n=&\ C_n^0+C_n^1\i+C_n^2\i^2+C_n^3\i^3+
    \cdots + C_n^n\i^n  \\
    =&\ C_n^0+C_n^1\i-C_n^2-C_n^3\i+
    \cdots + C_n^n\i^n  \\
    =&\ (C_n^0-C_n^2+C_n^4-\cdots)+\i (C_n^1-C_n^3+C_n^5-\cdots)
\end{align*}
因为$ 1+\i=\sqrt{2}\left(\cos\dfrac{\pi}{4}+
\i\sin\dfrac{\pi}{4}\right) $，利用\eqref{欧拉公式n倍角情形}式，
有$ (1+\i)^{n}=\sqrt{2^{n}}\left(\cos\dfrac{n\pi}{4}
+\i\sin\dfrac{n\pi}{4}\right) $，于是
\begin{align*}
    (1+\i)^{n}
    =&\ (C_n^0-C_n^2+C_n^4-\cdots)+\i (C_n^1-C_n^3+C_n^5-\cdots)\\
    =&\ \sqrt{2^{n}}\cos\dfrac{n\pi}{4}
    +\i\sqrt{2^{n}}\sin\dfrac{n\pi}{4}
\end{align*}
比较实部和虚部就能得到两个等式：
\begin{gather*}
    C_n^0-C_n^2+C_n^4-\cdots=\sqrt{2^{n}}\cos\dfrac{n\pi}{4} \\
    C_n^1-C_n^3+C_n^5-\cdots=\sqrt{2^{n}}\sin\dfrac{n\pi}{4}
\end{gather*}

\item 正整数的分拆是指将一个正整数分成几个正整数的和。即
\begin{align*}
    n=n_1+n_2+\cdots n_k \quad (n_i>0,\ 1\leq i\leq k)
\end{align*}
$ n_i $叫做该分拆的分部量。如果将各个$ n_i $任意交换位置后，仍然视为同一种表示法，
这样的分拆叫做\textbf{无序分拆}，否则称之为\textbf{有序分拆}。
对于有序分拆，可以视为排成一行的$ n $件物品，向它们的$ n-1 $个
间隔中插入$ k-1 $块隔板，将物品分成$ k $组，所以有序分拆的方法数为$ C_{n-1}^{k-1} $. 
无序分拆比较复杂，可查阅许胤龙、孙淑玲编著的《组合数学引论》。

\item \textbf{容斥原理}： 集合$A,\ B,\ A\cup B,\ A\cap B$中的
元素个数依次记为$ \mathrm{card}(A) $，$\mathrm{card}(B) $，
$\mathrm{card}(A\cup B)$，$\mathrm{card}(A\cap B) $，那么有
\begin{gather}\label{容斥原理公式}
    \mathrm{card}(A\cup B)=\mathrm{card}(A)+\mathrm{card}(B) 
    -\mathrm{card}(A\cap B)
\end{gather}
请结合下图理解：
\begin{figure}[H]
    \centering
    \includegraphics[width=0.3\linewidth]{PDF_Picture/韦恩图-交集}
\end{figure}
我们通过一个具体的例子来理解容斥原理。
两个正整数互质(互素)是指两个数的最大公因子是1
(所以1与任何正整数都是互质的)，
考虑小于等于28且与28互质的正整数的个数，
不过，直接考虑互质的数会比较麻烦，
让我们考虑小于等于28且与28不互质的数。
28的质因子是2和7，28以内所有2的倍数或7的倍数
都与28不互质，2的倍数有14个，
7的倍数有4个，能不能说2的倍数或7的倍数一共$ 14+4=18 $个呢？
不能！因为14和28都既是2的倍数、又是7的倍数，刚刚被算了2次，
得减掉，于是2的倍数或7的倍数一共$ 14+4-2=16 $个，互质的数的
个数就是$ 28-16=12 $，这12个数依次是1，3，5，9，11，13，15，17，
19，23，25，27. 请读者按上面的方法说明，小于等于30且与30互质的
数的个数是8\footnote{这8个数依次是$ 1,7,11,13,17,19,23,29 $.\q 
    8又恰好是一个字节包含的bit数，这个性质可以用来实现一个巧妙的算法，
    参见本书作者写的文章《30个整数映射到1个字节，
    查表法实现小范围内常数时间素性判定》\\
    https://zhuanlan.zhihu.com/p/19939334005 }.

\item 小于等于$ n $且与$ n $互质的正整数的
个数被定义为欧拉函数$ \varphi(n) $. 
若$ p,q $ 都是质数且不相等，$ k $是正整数，则
\begin{align*}
    & \varphi(p)=p-1 \\
    & \varphi(pq)=pq-p-q+1=(p-1)(q-1) \\
    & \varphi(p^k)=p^k-p^{k-1}=p^{k-1}(p-1)
\end{align*}

\item 正整数$ n $可以分解成其质因子的幂的乘积的形式，
$ n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k} $，比如
$ 28=2^2\times 7,\ 30=2\times 3\times 5,\ 12375=3^2\times 5^3 \times 11 $，
那么
\begin{gather}\label{eulerPhi函数的计算公式}
    \varphi(n)=n\left(1-\dfrac{1}{p_1}\right)
    \left(1-\dfrac{1}{p_2}\right)\cdots \left(1-\dfrac{1}{p_k}\right)
\end{gather}
比如
\begin{align*}
    \varphi(28)&=28\left(1-\dfrac{1}{2}\right)\left(1-
    \dfrac{1}{7}\right) \\
    &=28\left(1-\dfrac{1}{2}-\dfrac{1}{7}+\dfrac{1}{2\times 7}\right) \\
    &=28-\left(\dfrac{28}{2}+\dfrac{28}{7}-\dfrac{28}{2\times 7}
    \right)=12 \\
    \varphi(30)&=30\left(1-\dfrac{1}{2}\right)
    \left(1-\dfrac{1}{3}\right)\left(1-\dfrac{1}{5}\right) \\
    &=30\left(1-\dfrac{1}{2}-\dfrac{1}{3}-\dfrac{1}{5}+
    \dfrac{1}{2\times 3}+\dfrac{1}{2\times 5}+\dfrac{1}{3\times 5}
    -\dfrac{1}{2\times 3\times 5}\right) \\
    &=30-\left(\dfrac{30}{2}+\dfrac{30}{3}+\dfrac{30}{5}-
    \dfrac{30}{2\times 3}-\dfrac{30}{2\times 5}-\dfrac{30}{3\times 5}
    +\dfrac{30}{2\times 3\times 5}\right)
    =8
\end{align*}

\item 有$ n $级台阶，每次只允许上1级或2级，总共有多少种走法？\\
\textbf{解}\ 该问题可视为正整数$ n $的有序分拆，
同时要求所有的分部量小于等于2，
但直接使用隔板法，会面临无法限制分部量的大小的问题。
现改为寻找递推关系：到达第$ n $级台阶，
可能是从第$ n-2 $级台阶再上2级到达的，
也可能是从第$ n-1 $级台阶再上1级到达的，令$ F_n $
代表上$ n $级台阶的方法数，那么$ F_n=F_{n-1}+F_{n-2} $，
这正是斐波那契数列的递推关系，$ F_1=1,\ F_2=2 $，
相当于常规的斐波那契数列($ F_1=1,F_2=1 $)从第2项开始。

\item 汉诺塔问题：现有A、B、C三根立柱以及$ n $个大小不等的中空圆盘，
这些圆盘从小到大套在A柱上形成一座塔(小圆盘在上，大圆盘在下)，
要求把$ n $个圆盘从A柱上搬到C柱上，
并仍然保持下大上小的顺序。要求每次只能从一根立柱上拿下一个圆盘放到另外一根
立柱上，且不允许大盘压在小盘上，至少要搬多少次？\\
\textbf{解}\ 设$ H(n) $表示有$ n $个圆盘时最小的搬动次数，整个搬动过程可
分成三个阶段：\\
(一) 将套在A柱上面的$ n-1 $个圆盘从A柱搬到B柱，搬动次数为$ H(n-1) $；\\
(二) 把A柱最下面的圆盘搬到C柱上，搬动次数为1；\\
(三) 把B柱上的$ n-1 $个圆盘搬到C柱上，搬动次数为$ H(n-1) $；\\
于是递推关系为：$ H(n)=2H(n-1)+1 $，初始条件为$ H(1)=1 $. 因为
\begin{align*}
    H(n)+1=2[H(n-1)+1]=2^2[H(n-2)+1]=\cdots=2^{n-1}[H(1)+1]=2^n
\end{align*}
所以，$ H(n)=2^n-1 $. 

\item 令数列 $ \{ a_k \} (1\leq k \leq n) $是集合
$ \{ 1,2,\cdots n \} $的一个排列，
如果每个元素都不在其对应下标的位置上，即$ a_k\neq k $，
那么这种排列称为错位排列，或错排。1 2 3 4的错排有:
\begin{table}[h]
    \centering
    \begin{tabular}{ccc}
        4 3 2 1 & 4 3 1 2 & 4 1 2 3 \\
        3 4 2 1 & 3 4 1 2 & 3 1 4 2 \\
        2 1 4 3 & 2 3 4 1 & 2 4 1 3 
    \end{tabular}
\end{table} \\
设$ n $个元素错排的方案数为$ D_n $，第一步，考虑元素$ a_n $，
把它放在除第$ n $位以外的某个位置，比如位置$ k $，
一共有$ n-1 $种放法；第二步，考虑元素$ a_k $，这时有两种情况：
(1)把它放到位置$ n $，此时$ k,n $两个位置分别被$ a_n,a_k $占据，
已经错位了，那么剩下$ n-2 $个元素错排即可，有$ D_{n-2} $种排法；
(2)元素$ a_k $不放到位置$ n $(可把元素$ a_k $想象成不能出现在
第$ n $位的一个新的$ a_n $)，这时对除$ a_n $以外的$ n-1 $
个元素错排，有$ D_{n-1} $种排法。根据乘法和加法原理，
$ D_n=(n-1)(D_{n-1}+D_{n-2}),\ D_1=0,\ D_2=1. $
\begin{gather*}
    D_n-nD_{n-1}=(-1)[D_{n-1}-(n-1)D_{n-2}]=\cdots =(-1)^{n-2}[D_2-D_1]=(-1)^n 
\end{gather*}
首尾同除$ n! $，
\begin{gather*}
    \dfrac{D_n}{n!}-\dfrac{D_{n-1}}{(n-1)!}=\dfrac{(-1)^n}{n!} 
\end{gather*}
取$ n-1 $个这样的式子相加：
\begin{align}\label{错排通项公式}
    D_n=n!\left[ 1-\dfrac{1}{1!}+\dfrac{1}{2!}-\cdots 
    +(-1)^n\dfrac{1}{n!}\right] 
\end{align}
上式也可用数学归纳法证明。

%常考题型，对$ \left(ax^{\alpha}+by^{\beta} \right)^n $的展开式，求所有系数的和，奇数项系数的和，
%偶数项系数的和，所有系数绝对值的和，常数项。方法：令$ x,y=-1,0,1 $这三个特殊值，以及令
%$ ax^{\alpha}+by^{\beta} =0 $. \\
%\item \  
% $ (2x+3x^2)^6=c_0+c_1 $
% 另一类问题是，

\item 环形染色问题：将一个圆分成$n(n\geq 2)$个不同的扇形区域，
现用$m(m\geq 2)$种不同颜色对这$n$个区域染色，要求一个扇形区域
使用一种颜色，相邻区域颜色不同，则不同的染色方法数是
\begin{gather}\label{环形染色方法数公式}
    (m-1)^n + (-1)^n(m-1) 
\end{gather}
\textbf{证}\ 将$n$个不同的扇形区域依次记为$A_1,A_2,\cdots,A_n$，
将$A_1$区域先染色，有$m$种选择，$A_2$区域有$m-1$种选择，
$A_3$区域有$m-1$种选择，……，$A_{n-1}$区域有$m-1$种选择，
$A_n$区域有$m-1$种选择，则不同的染色方法有$m(m-1)^{n-1}$种，
但这里面会包含两种情况：\\
(一) $A_1,A_n$区域不同色，设不同的染色方法有$a_n$种。\\
(二) $ A_1,A_n $ 区域同色，则不同的染色方法有 $ a_{n-1} $ 种。\\
于是
\begin{gather*}
    a_n+a_{n-1} = m(m-1)^{n-1} 
\end{gather*}
接下来用两种方法求出$a_n$的表达式。\\
\textbf{方法一}
\begin{align*}
    a_n=-a_{n-1} + m(m-1)^{n-1} =&\ -a_{n-1}+[(m-1)+1](m-1)^{n-1}\\
    =&\ -a_{n-1} + (m-1)^n + (m-1)^{n-1}
\end{align*}
于是
\begin{align*}
    a_n - (m-1)^n = (-1)\left[a_{n-1} - (m-1)^{n-1}\right]
\end{align*}
所以数列 $\{a_n - (m-1)^n\}$ 是以$a_2-(m-1)^2 = m(m-1)-(m-1)^2=m-1$
为首项，公比为 $-1$ 的等比数列，故
\begin{gather}
    a_n - (m-1)^n = (m-1)(-1)^{n-2} = (m-1)(-1)^n \notag \\
    a_n = (m-1)^n + (-1)^n(m-1) \label{环形染色-an统一表达式}
\end{gather}
\textbf{方法二}
\begin{align*}
    a_n+a_{n-1} &= m(m-1)^{n-1}  \\
    a_{n-1}+a_{n-2} &= m(m-1)^{n-2} 
\end{align*}
两式相减有：$a_{n}-a_{n-2}=m(m-2)(m-1)^{n-2} $. 即
\begin{align*}
    a_{2k+1}-a_{2k-1} &= m(m-2)(m-1)^{2k-1} \\
    a_{2k}-a_{2k-2}   &= m(m-2)(m-1)^{2k-2} 
\end{align*}
易知$a_2=m(m-1)$，$a_3=m(m-1)(m-2)$，于是
\begin{align*}
    a_{2k+1}-a_3=&\ m(m-2)\sum_{i=2}^{k}(m-1)^{2i-1}=
    m(m-2)\cdot\dfrac{(m-1)^3-(m-1)^{2k+1}}{1-(m-1)^2} \\
    =&\ (m-1)^{2k+1}-(m-1)^3 
\end{align*}
\begin{gather} \label{环形染色-奇数情形}
    a_{2k+1} = (m-1)^{2k+1}-(m-1) 
\end{gather}
\begin{align*}
    a_{2k}-a_2=&\ m(m-2)\sum_{i=2}^{k}(m-1)^{2i-2}=
    m(m-2)\cdot\dfrac{(m-1)^2-(m-1)^{2k}}{1-(m-1)^2} \\
    =&\ (m-1)^{2k}-(m-1)^2 
\end{align*}
\begin{gather} \label{环形染色-偶数情形}
    a_{2k} = (m-1)^{2k}+(m-1) 
\end{gather}
\eqref{环形染色-奇数情形}式和\eqref{环形染色-偶数情形}式可以统一写成
\eqref{环形染色-an统一表达式}式。

上面介绍的上台阶、汉诺塔、错排、环形染色四个问题，如果试图直接寻找答案，无疑是相当困难的，而寻找递推关系则要简单得多。

\item $ \left(ax^{\alpha}+bx^{\beta} \right)^n $的展开式的通项为
$ T_{r+1}=C_n^ra^{n-r}b^rx^{(n-r)\alpha+r\beta} $，
设$ C_n^m a^{n-m}b^m $是最大的系数，则
\begin{align}\label{二项式系数最大值不等式组-首次出现}
\begin{dcases}
    C_n^m a^{n-m}b^m\geq C_n^{m-1} a^{n-m+1}b^{m-1} \\
    C_n^m a^{n-m}b^m\geq C_n^{m+1} a^{n-m-1}b^{m+1}
\end{dcases}
\end{align} 
\begin{align}\label{二项式系数最大值不等式组的解}
    \begin{dcases}
        \dfrac{b}{m}   \geq \dfrac{a}{n-m+1} \\
        \dfrac{a}{n-m} \geq \dfrac{b}{m+1}
    \end{dcases} \quad \Rightarrow \quad 
    \dfrac{bn-a}{a+b} \leq m \leq \dfrac{bn+b}{a+b}
\end{align} 
因为$ \dfrac{bn-a}{a+b}+1=\dfrac{bn+b}{a+b} $，所以不等式组一定有解。
当$ \dfrac{bn-a}{a+b} $为整数时，有两个解；否则只有一个解。
例如，$ (2x+5x^2)^{12} $展开式中系数最大的项是
$ C_{12}^{3}(2x)^3(5x^2)^9=3437500000x^{21} $，所有系数的图像如下
\footnote{对于高考中允许使用计算器的省份，则可以直接使用计算器的表格(Table)功能，
    定义$ f(x)= 12Cx\times 2^{12-x}\times 5^x,\ x=0\sim 12 $即可。}：
%syms x;
%plot([0:12],fliplr(coeffs(expand((2*x+5*x^2)^12))),'k.','markersize',15);
%axis([-1 13 -10^8 3.6*10^9]);grid on
\begin{figure}[H]
    \centering
    \includegraphics[width=0.5\linewidth]{二项式系数最大}
\end{figure} 

\item 设随机变量$ X $服从二项分布$ b(n,p) $，每次实验时，事件$ A $发生的概率为
$ p $，那么在$ n $次实验中事件$ A $发生$ k $次的概率为
\begin{align*}
    P\{X=k\}=C_n^kp^k(1-p)^{n-k}
\end{align*}
若想找出$ k $为何值时概率最大，可采用与不等式组(\ref{二项式系数最大值不等式组-首次出现})
一样的方法，可解得：
\begin{align*}
    (n+1)p-1\leq k \leq (n+1)p 
\end{align*}


\item $^*$ 一个正方形无法划分为奇数个面积相等的三角形
\footnote{参见 Paul Monsky, On dividing a square into triangles, Amer. Math. Monthly 77 (1970), no. 2, 161–164. 或者参见 https://zhuanlan.zhihu.com/p/398055396 . }。

\item $^*$ 设$ f(x) $在区间$ [0,1] $上连续不断，则多项式
\begin{gather*}
    \sum_{k=0}^{n}f\left(\dfrac{k}{n}\right)C_n^kx^k(1-x)^{n-k}
\end{gather*}
被称为伯恩斯坦(Bernstein)多项式，当$ n $增大时，该多项式可以越来越接近$ f(x) $本身。

\item $^*$ 在核磁共振(Nuclear Magnetic Resonance, NMR)现象中，
当一个氢原子核有$ n $个临近的全同氢原子核存在时，其NMR吸收峰分裂为
$ n+1 $个，各峰的强度之比为
$ C_n^0:C_n^1:C_n^2:\cdots :C_n^n $，该规律被称为自旋裂分$ n+1 $规律。

\item $^*$ 计算任意烷烃$ \mathrm{C_nH_{2n+2},\ n}\in \textbf{N}^+ $
的同分异构体数量是一个比较困难但意义不大的问题，当$ n=1\sim 10 $时，
同分异构体数量依次为1，1，1，2，3，5，9，18，35，75.
目前只能递推计算，找不出通项公式。

\end{itemize}

\section{例题}
\begin{enumerate}[label={【\textbf{例\thechapter.\arabic*}】},
 leftmargin=\inteval{\myenumleftmargin}pt,
 itemsep=\inteval{\myenumitempsep}pt,
 itemindent=\inteval{\myenumitemindent}pt]
 
\item 到四面体的四个顶点距离相等的平面个数是多少？ 
\begin{figure}[H]
    \centering
    \includegraphics[width=0.4\linewidth]{四面体_中位面}
\end{figure}
\textbf{解}\ 与4个顶点等距的平面可分为两类：\\
(一) 平面的一侧有1个顶点，另一侧有3个顶点。比如$ \Delta EFG $所在平面，
此类平面由共用同一个顶点的三条棱的中点确定(称为四面体的中位面)，
此类平面的数量其实就是把4个顶点分成1+3两组的方法数，
分组方法为$ A|BCD,\ B|ACD,\ C|ABD,\ D|ABC $，共4种；\\
(二) 平面的一侧有2个顶点，另一侧也有2个顶点。
取特定的4条棱的中点，比如$ EHIG $，就能得到这一类平面。
此类平面的数量其实就是把4个顶点平均分成两组的方法数，
分组方法为$ AB|CD,\ AC|BD,\ AD|BC $，共3种；\\
故一共有7张不同平面到四个顶点距离相等。\\
\textbf{注}：$ S_{\Delta EFG}=\dfrac{1}{4}S_{\Delta CDB},\ 
V_{A-EFG}=\dfrac{1}{8}V_{A-CDB} $. 

\item 四面体的顶点与棱的中点共10个点，在其中取4个不共面的点，
有多少种不同的取法？\\
\textbf{解}\ 10个点中任取4点，有$ C_{10}^4=210 $种取法。考虑4点共面的情况：\\
(一) 4点在四面体的同一个面上，有$ 4C_6^4=60 $种；\\
(二) 4点中3点在同一条棱上(比如$ A,E,C $)，剩下一点在对棱中点上(比如$ I $)，有6种；\\
(三) 同上一道例题的情形(二)，有3种。\\
所以，不共面的取法有$ 210-60-6-3=141 $种。
\bigskip

\textbf{平均分组问题}： 将$na$个物品平均分成$n$组，每组$a$个，
则分组方法数为
\begin{gather}\label{平均分组方法数}
    \dfrac{C_{na}^aC_{(n-1)a}^a\cdots C_{2a}^a}{n!}
\end{gather}
特别注意，要除以$n!$，不能不除，也不是除以$n$. 
比如3个物品平均分成3组，如果不除以$3!$，那就是$C_3^1C_2^1=6$，
这显然是错误的，因为3个物品平均分成3组只有1种方法。

\textbf{相邻元素捆绑法}： 题目要求某些元素必须相邻，
就可以把相邻的元素捆在一起，当成一个大元素参与排列。
分组与捆绑往往同时出现。

\item (1) 12本不同的书按$3:3:2:2:2$的比例分给五个人(每个人都可以
拿到2本或3本)，有多少种不同的分法？
 \ $\left(\dfrac{C_{12}^3C_9^3C_6^2C_4^2}{2!
    \cdot 3!} P_5^5\right) $ \\
(2) 7本不同的书按$1:2:4$分成三组，有多少种不同的分法？
   \ ($C_7^1C_6^2C_4^4$) \\
(3) 7本不同的书按$1:2:4$分别分给A、B、C三个人，
有多少种不同的分法？\ ($C_7^1C_6^2C_4^4$) \\
(4) 7本不同的书分给3人，1人1本，1人2本，1人4本,有多少种分法？
   \ ($C_7^1C_6^2C_4^4 P_3^3$)


\item 将5名志愿者分配到3个不同的奥运场馆参加接待工作，
每个场馆至少分到一名志愿者的方案有多少种？ \\
\textbf{解}\ 这属于整数的有序分拆，对应的无序分拆有
$1+1+3$和$1+2+2$这两种，再把顺序考虑进来即可。\\
(一) 先从5个人中选出3个，绑在一起，然后与剩余两人一起排列，
共$C_5^3P_3^3=60$种；\\
(二) 先从5个人中选出2个，绑在一起，
再从剩余3个人中选出2个，绑在一起，然后与剩余1人一起排列。
同时这里包含一个$2+2$的平均分组，
所以共$\dfrac{C_5^2C_3^2}{2!}P_3^3=90$种；\\
综合(一)和(二)，共有150种。
\bigskip

\textbf{不相邻元素插空法}： 题目要求某些元素必须不相邻，
可以先把允许相邻的元素全排列，再把要求不相邻的元素插到
其余元素之间的空档(和两端)。

\item 马路上有编号为1、2、3、…、10的十盏路灯，为节约用电又不影响照明，
可以把其中3盏灯关掉，但不可以同时关掉相邻的两盏，
在两端的灯都不能关掉的情况下，有多少种不同的关灯方法？\\
\textbf{解}\ 等价于在7只亮着的路灯之间的6个空档中插入3只
熄掉的灯，故所求方法总数为$  C_6^3= 20 $.
\bigskip

\textbf{定序问题}： 某些元素的先后顺序已经被规定。

\item A,B,C,D,E,F六个人站成一排拍照，要求A必须在B的左侧，
一共多少种排列方法？ \\
\textbf{解}\ A在B的左侧与A在B的右侧的方法数相同，都是6人全排列的
一半，即$\dfrac{1}{2}P_6^6=360$.

\item 有10个翻译，其中3人只能译英语，2人只能译法语，
另5人既能译英语又能译法语，现欲从中
选取2名英语和3名法语翻译，有几种选法？\\
\textbf{解}\ 针对既能翻译英语又能翻译法语的5人进行分类：\\
5人中选1人译法语，有$ C_5^1C_2^2C_7^2 = 105 $种选法；\\
5人中选2人译法语，有$ C_5^2C_2^1C_6^2 = 300 $种选法；\\
5人中选3人译法语，有$ C_5^3C_5^2= 100 $种选法； \\
所以共有$ 105 + 300 + 100 = 505 $种选法。\\
(请按5人中选1人和2人译英语的分类方法再算一遍。)


\item 下图的矩形由$ 3\times 5 $个正方形组成，则从$ M $点到$ N $点
的最短路径有多少种？
\begin{figure}[H]
    \centering
    \includegraphics[width=0.3\linewidth]{正方形网格走对角顶点}
\end{figure}
\textbf{解}\ 从$ M $到$ N $必须向上走3步，向右走5步，共走8步。
只要从8步中选出3步向上走(或者5步向右走)，就可以确定一种走法，比如
$\uparrow\rightarrow\rightarrow\uparrow\rightarrow\rightarrow
\rightarrow\uparrow $，所以答案为
$ C_8^3=C_8^5=56 $．

\item (1) 数轴上有一个质点从原点出发，每次向正方向或负方向跳1个单位，
经过12次跳动，质点落在刻度为4的点(允许重复过此点)，
则质点不同的运动方法共有多少种？ \\
(2) 数列$\{a_n\}$共有13项，$a_1 = 0,\ a_{13} = 4$且
$ |a_{n+1}-a_n|=1,\ n=1,2,\cdots,12 $，满足这些条件
的不同数列有多少个？\\
\textbf{解}\ 这两个问题的本质是完全一样的，而且与上一道例题类似。
$ |a_{n+1}-a_n|=1 $
就相当于每次向正方向或负方向跳1个单位，从$a_1$到$a_{13}$需要12次跳动。
假设正方向跳动了$x$次，负方向跳动了$y$次(相当于把上一道例题中向上的箭头换成
向左的箭头)，那么$\begin{dcases}
    x+y=12 \\
    x-y=4
\end{dcases} \ \Rightarrow \ \begin{dcases}
    x=8 \\
    y=4
\end{dcases} $，所以，不同的跳动方法(不同的数列)共有$C_{12}^4=495 $种。

\item $^*$ 数轴上有一个质点从原点出发，每次只能向正方向跳127个单位或者
向负方向跳101个单位。质点最少需要跳多少次，才能到达刻度为1的点？\\
\textbf{解}\ 假设正方向跳动了$x$次，负方向跳动了$y$次，那么
$ 127x-101y=1 $，现在需要寻找这个不定方程的正整数解，并使得$x+y$为最小。
使用辗转相除法，即不断进行带余除法，直到余数为1，
\begin{align*}
    127\div 101 &=1 \cdots\cdots 26 \\
    101\div  26 &=3 \cdots\cdots 23 \\
    26\div  23 &=1 \cdots\cdots 3 \\
    23\div   3 &=7 \cdots\cdots 2 \\
    3\div   2 &=1 \cdots\cdots 1 
\end{align*}
然后从最后的1出发，逐步回退，
\begin{align*}
    1 &= 3-2\times 1 \\
    &= 3-(23-3\times7)\times 1 \\
    &= 3\times 8-23\times 1\\
    &= (26-23\times1)\times 8-23\times 1\\
    &= 26\times 8-23\times 9 \\
    &= 26\times 8-(101-26\times 3)\times 9  \\
    &= 26\times 35-101\times 9  \\
    &= (127-101\times1)\times 35-101\times 9  \\
    &= 127\times 35-101\times 44
\end{align*}
$ 127\times(35+101n)-101\times(44+127n)=1 $，即$ 127x-101y=1 $的通解是
\begin{gather*}
    \begin{dcases}
        x=35+101n \\
        y=44+127n
    \end{dcases},\ n\in\mathbf{Z}
\end{gather*}
要让$x,y$为正整数，$n$必须非负，
所以$x+y$的最小值为$35+44=79$，质点最少需要跳动79次。\\
\textbf{注}\ 贝祖(Bezout)等式：设$ a,b $是非零整数，$ d=\gcd(a,b) $
代表$ a,b $的最大公约数，那么存在整数$ x,y $，满足$ ax+by=d $. 
比如，$ a=697,\ b=391,\ d=\gcd(697,391)=17,\ 9\times 697+(-16)\times 391=17 $. 

\item 如下图所示，一个圆被分成5个不同的区域，要求用4种颜色对这5个
区域进行染色，存在公共边的区域不能使用相同的颜色，有多少种不同的
染色方案？
\begin{figure}[H]
    \centering
    \includegraphics[width=0.25\linewidth]{PDF_Picture/环形染色-4个扇形}
\end{figure}
\textbf{解}\ 先对中央区域进行染色，有4种选择，再用剩下的3种颜色对
周围的4个区域进行环形染色，根据\eqref{环形染色方法数公式}式，有
$ (3-1)^4+(3-1)=18 $种方法，总共有$ 4\times 18=72 $种方法。
\bigskip

\textbf{圆排列问题}：把$n$个不同元素放在圆周上的$n$个地位平等
的位置上，特点是\underline{不存在起点}
\underline{和终点}，如果把一种排列
方法旋转一定角度后能得到另一种排列方法，那就认为这两种排列方法
是同一种。比如$(a,b,c,d); (b,c,d,a); (c,d,a,b); (d,a,b,c)$
就是同一种圆排列。$n$个不同元素做直线全排列的方法数为$n!$，
某个元素(比如$a$元素)可以出现在$n$个位置的任意一个，
但$a$出现在$n$个不同的(直线)位置却可以是同一种圆排列，所以
$n$个不同元素的圆排列方法数为$\dfrac{n!}{n}=(n-1)!$.

\item $^*$假设某监狱里关押了100名囚犯，他们的编号为1到100. 
某一天，监狱管理者决定给他们一次出狱的机会，但要遵循以下规则：\\
(一)、有100张卡片，分别写有整数1到100. 同时有100个盒子，
盒子上也分别写有整数1到100. 将100张卡片随机地放到100个盒子中，
而且每个盒子内只有一张卡片。将这100个装有卡片的的盒子放在一个房间里。\\
(二)、每次有一名囚犯进入上述房间，他可以打开至多50个盒子，查看里面
的卡片上的数字，然后盖上盒子(不得在盒子上留有任何标记，不得取出卡片)，
离开房间。离开房间后的囚犯不得向其他囚犯传递任何信息。
如果房间里的囚犯能在打开的盒子中找到写有自身编号的卡片，
那么称这名囚犯的状态为“成功”，否则称为“失败”。\\
(三)、如果所有囚犯的状态都是“成功”，那么所有囚犯都能获得释放；
只要有一个囚犯的状态是“失败”，那么所有囚犯都要继续关押。\\
这100名囚犯该采取什么开盒策略，才能提高所有人一起获得释放的概率？\\
\textbf{解}\ 如果每个囚犯都是随机开50个盒子，那么这100人被释放的
概率为$\left(\dfrac{1}{2}\right)^{100}\approx 7.9\times 10^{-31} $，
几乎为0，所以随机打开的策略是毫无意义的。 \\
最优的策略如下
\footnote{下面这篇文章证明了此策略是最优的：Warshauer, M., Curtin, E. The locker puzzle. The Mathematical Intelligencer 28, 28–31 (2006). https://www.cl.cam.ac.uk/$\sim $gw104/Locker\_Puzzle.pdf }：每个囚犯首先寻找编号与自身编号(设为$a$)相同的盒子并打开，
设里面的卡片上的数字为$b$，如果$b=a$，那就已经成功了。
如果$b\neq a$，就去打开编号为$b$的盒子，设里面的卡片上的数字
为$c$，如果$c\neq a$，那就去打开编号为$c$的盒子……这样一直做下去，
直到找到写有自身编号$a$的卡片，或者累计打开了50个盒子。\\
我们先用10名囚犯和10个盒子(允许开5个盒子)来解释一下上述策略是怎么执行的。
假设10个盒子中随机装入的卡片编号如下：
\begin{table}[H] 
    \centering
    \renewcommand\arraystretch{1}
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
        \hline
        盒子编号  & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
        \hline
        盒内卡片编号  & 7 & 5 & 2 & 1 & 10 & 8 & 4 & 6 & 3 & 9  \\
        \hline
    \end{tabular}
\end{table}
\vspace{-4mm}
编号为1的囚犯的开盒顺序：$ 1 \to 7 \to 4 $，打开了3个盒子，已成功。
因为$ 1 \to 7 \to 4 \to 1$构成了一个闭环，那么编号为7和4的囚犯也只需要
打开3个盒子就能成功。\\
编号为2的囚犯的开盒顺序：$ 2 \to 5 \to 10 \to 9 \to 3 $，
打开了5个盒子，已成功。因为$ 2 \to 5 \to 10 \to 9 \to 3 \to 2$
构成了一个闭环，那么编号为5、10、9、3的囚犯也只需要
打开5个盒子就能成功。\\
编号为6的囚犯的开盒顺序：$ 6 \to 8 $，打开了2个盒子，已成功。
编号为8的囚犯也只需要打开2个盒子就能成功。\\
上面一共存在3个闭环，环的长度依次为3, 5, 2, 最大的环的的长度没有超过5，
此时囚犯是可以全部释放的。让我们再看另一个情形：
\begin{table}[H] 
    \centering
    \renewcommand\arraystretch{1}
    \begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
        \hline
        盒子编号  & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
        \hline
        盒内卡片编号  & 6 & 7 & 5 & 8 & 2 & 9 & 3 & 10 & 4 & 1  \\
        \hline
    \end{tabular}
\end{table}
\vspace{-4mm}
此时一共存在2个闭环，分别是
\begin{align*}
    & 2 \to 7 \to 3 \to 5 \to 2 \\
    & 1 \to 6 \to 9 \to 4 \to 8 \to 10 \to 1
\end{align*}
环的长度依次为4,6，最大的环的的长度超过了5，
此时囚犯是无法释放的。\\
100名囚犯获得释放的概率，取决于100张卡片在100个盒子中全排列以后，
形成的环的最大长度是否超过了50. 现在来考虑形成长度为$n\ (n>50)$
的环的概率，先从100张卡片中选出$n$张进行圆排列，然后对剩余的
$100-n$张进行全排列，方法数为$C_{100}^n\cdot (n-1)!\cdot (100-n)!$，
概率为$ \dfrac{C_{100}^n\cdot (n-1)!\cdot (100-n)!}{100!}=\dfrac{1}{n} $.
所以，环的最大长度不超过50的概率(100名囚犯获得释放的概率)为
\begin{gather*}
    1-\left[\dfrac{1}{51}+\dfrac{1}{52}+\cdots+
    \dfrac{1}{100}\right]\approx 0.3118
\end{gather*}
读者如果学习过C语言的多级指针或链表，就可以用来与这个问题进行类比了。

\item \label{C_2n^1357都是偶数} 
设$m,n$均为正整数，且$m\leq n$，求证：
$ C_{2n}^{2m-1} $永远为偶数。\\
\textbf{证}\ 利用组合数的递推关系，
\begin{align*}
    C_{2n}^{2m-1} &=C_{2n-1}^{2m-2}+C_{2n-1}^{2m-1}  \\
    &=(C_{2n-2}^{2m-3}+C_{2n-2}^{2m-2})+(C_{2n-2}^{2m-2}+C_{2n-2}^{2m-1}) \\
    &=C_{2n-2}^{2m-3}+C_{2n-2}^{2m-1}+
    \underbrace{2C_{2n-2}^{2m-2}}_{\text{偶数}} 
\end{align*}
利用上式，因为$C_4^1=C_4^3=4$为偶数，那么$C_6^3=C_4^1+C_4^3+2C_4^2$也是偶数。
又因为$ C_{2n}^1=C_{2n}^{2n-1}=2n $显然是偶数，
即$C_6^1,C_6^3,C_6^5$都是偶数。\\
同理，$ C_8^3=C_8^5=C_6^1+C_6^3+2C_6^2 $是偶数，
于是$C_8^1,C_8^3,C_8^5,C_8^7$都是偶数。\\
这个递推过程可以一直做下去，由数学归纳法，$ C_{2n}^{2m-1} $永远为偶数。

\item $^*$ 观察下列等式：
\begin{align*}
    &(\sqrt{2} \pm 1)^{1}=\sqrt{2} \pm \sqrt{1} \\
    &(\sqrt{2} \pm 1)^{2}=3 \pm 2\sqrt{2}=\sqrt{9} \pm \sqrt{8} \\
    &(\sqrt{2} \pm 1)^{3}=5\sqrt{2} \pm 7=\sqrt{50} \pm \sqrt{49} \\
    &(\sqrt{2} \pm 1)^{4}=17 \pm 12\sqrt{2}=\sqrt{289} \pm \sqrt{288} \\
    & \q\q \vdots \\
    &(\sqrt{3} \pm \sqrt{2})^{1}=\sqrt{3} \pm \sqrt{2} \\
    &(\sqrt{3} \pm \sqrt{2})^{2}=5 \pm 2\sqrt{6}=\sqrt{25} \pm \sqrt{24} \\
    &(\sqrt{3} \pm \sqrt{2})^{3}=9\sqrt{3} \pm 11\sqrt{2}=\sqrt{243} \pm 
    \sqrt{242} \\
    &(\sqrt{3} \pm \sqrt{2})^{4}=49 \pm 20\sqrt{6}=\sqrt{2401} \pm \sqrt{2400}    
\end{align*}
求证：$ (\sqrt{n}\pm\sqrt{n-1})^k=\sqrt{N}\pm\sqrt{N-1} $，
$ n,k,N\in \textbf{N}^+ $. \\
\textbf{证}\ 以$ (\sqrt{n}+\sqrt{n-1})^{k} $
为例(当加号情形成立时，减号情形自动成立)，对$ k $用数学归纳法，
假设$ (\sqrt{n}+\sqrt{n-1})^k=\sqrt{N}+\sqrt{N-1} $成立，
当$ k $变成$ k+1 $时，
\begin{align*}
    (\sqrt{n}+\sqrt{n-1})^{k+1}&=(\sqrt{N}+\sqrt{N-1})(\sqrt{n}+\sqrt{n-1}) \\
    &=\sqrt{Nn}+\sqrt{N(n-1)}+\sqrt{n(N-1)}+\sqrt{(N-1)(n-1)}
\end{align*}
我们希望上式具有$ \sqrt{M}+\sqrt{M-1}\ (M\in \textbf{N}^+) $的形式，
依据上面的数值例子，有
\begin{align*}
    \sqrt{Nn}+\sqrt{(N-1)(n-1)} &=\sqrt{M}   \tag*{\ding{172}} \\
    \sqrt{N(n-1)}+\sqrt{n(N-1)} &=\sqrt{M-1} \tag*{\ding{173}}
\end{align*}
两边平方，
\begin{align*}
    Nn+2\sqrt{Nn(N-1)(n-1)}+Nn-(N+n)+1 &=M   \tag*{\ding{174}} \\
    Nn-N+2\sqrt{Nn(N-1)(n-1)}+Nn-n     &=M-1 \tag*{\ding{175}}
\end{align*}
可以发现\ding{174}式和\ding{175}式是等价的(\ding{172}式和\ding{173}式也是等价的)，那么
只需证明$ \sqrt{Nn(N-1)(n-1)} $是整数，由二项式定理和归纳假设，
\begin{align*}
    \sqrt{N} &=\dfrac{1}{2}\left[(\sqrt{n}+\sqrt{n-1})^k
    +(\sqrt{n}-\sqrt{n-1})^k\right] \\
    \sqrt{N-1} &=\dfrac{1}{2}\left[(\sqrt{n}+\sqrt{n-1})^k
    -(\sqrt{n}-\sqrt{n-1})^k\right] 
\end{align*}
所以，
{\small \begin{align*}
        &\ \sqrt{N(N-1)}\\
        =&\ \dfrac{1}{2}\left[(\sqrt{n}+\sqrt{n-1})^k
        +(\sqrt{n}-\sqrt{n-1})^k\right]\cdot
        \dfrac{1}{2}\left[(\sqrt{n}+\sqrt{n-1})^k
        -(\sqrt{n}-\sqrt{n-1})^k\right] \\
        =&\ \dfrac{1}{4}\left[(\sqrt{n}+\sqrt{n-1})^{2k}-
        (\sqrt{n}-\sqrt{n-1})^{2k}\right] \\  
        =&\ \dfrac{1}{2}\left[C_{2k}^1(\sqrt{n})(\sqrt{n-1})^{2k-1}
        +C_{2k}^3(\sqrt{n})^3(\sqrt{n-1})^{2k-3}+
        C_{2k}^5(\sqrt{n})^5(\sqrt{n-1})^{2k-5}+\cdots\right] \\
        =&\ \uwave{\dfrac{1}{2}\left[C_{2k}^1(\sqrt{n-1})^{2k-2}
            +C_{2k}^3(\sqrt{n})^2(\sqrt{n-1})^{2k-4}+
            C_{2k}^5(\sqrt{n})^4(\sqrt{n-1})^{2k-6}+\cdots\right]}
        \cdot\sqrt{n(n-1)}
\end{align*} }
根据\ref{C_2n^1357都是偶数}，
$ C_{2k}^1,C_{2k}^3,C_{2k}^5,\cdots $都是偶数，且上式中括号内
$ \sqrt{n},\sqrt{n-1} $的指数都是偶数，所以，划波浪线的部分必定是整数，
$ \sqrt{N(N-1)n(n-1)} $也必然是整数，证毕。

\item 用数学归纳法证明：\\
(1) $ n\in \textbf{N}^+ $，当$ n\geq 4 $时，$ C_{2n+1}^n<2^{2n-1} $. \\
(2)  $ n\in \textbf{N}^+ $，$ \dfrac{2^{2n-1}}{\sqrt{n}}\leq 
C_{2n}^n $.\\
\textbf{解}\ (1) 当$ n=4 $时，$ C_9^4=126<2^7=128 $，结论成立。
假设$ C_{2n+1}^n<2^{2n-1} $对$ n\geq 4 $成立，那么
\begin{align*}
    C_{2n+3}^{n+1}=&\ C_{2n+2}^{n}+C_{2n+2}^{n+1} \\
    =&\ (C_{2n+1}^{n-1}+C_{2n+1}^{n})+(C_{2n+1}^{n}+C_{2n+1}^{n+1}) \\
    =&\ C_{2n+1}^{n-1}+3C_{2n+1}^{n}\q (\text{因为}
    C_{2n+1}^{n}=C_{2n+1}^{n+1}) \\
    <&\ C_{2n+1}^{n}+3C_{2n+1}^{n} 
    = 4C_{2n+1}^{n}<4\cdot 2^{2n-1}=2^{2(n+1)-1}
\end{align*}
(2) 当$ n=1 $时，$ \dfrac{2^{2n-1}}{\sqrt{n}}=C_{2n}^n $，
假设$ \dfrac{2^{2n-1}}{\sqrt{n}}\leq C_{2n}^n $
对$ n\geq 1 $成立，那么
\begin{align*}
    C_{2n+2}^{n+1}=C_{2n+1}^{n}+C_{2n+1}^{n+1} 
    =(C_{2n}^{n-1}+C_{2n}^{n})+(C_{2n}^{n}+C_{2n}^{n+1}) 
    =2C_{2n}^{n-1}+2C_{2n}^{n} 
\end{align*}
因为$ C_{2n}^{n-1}=\dfrac{(2n)!}{(n-1)!\cdot (n+1)!}=\dfrac{n}{n+1}
\cdot \dfrac{(2n)!}{n!\cdot n!}=\dfrac{n}{n+1}C_{2n}^n $，所以，
\begin{align*}
    C_{2n+2}^{n+1}=2C_{2n}^{n-1}+2C_{2n}^{n} 
    =&\ 2\left(\dfrac{n}{n+1}+1\right)C_{2n}^n \\
    \geq &\ \dfrac{2(2n+1)}{n+1}\cdot\dfrac{2^{2n-1}}{\sqrt{n}} 
    > \dfrac{2^{2n+1}}{\sqrt{n+1}}
\end{align*}
其中，$ \dfrac{2n+1}{n+1}\cdot \dfrac{1}{\sqrt{n}}>\dfrac{2}{\sqrt{n+1}} $
是容易验证的。

\item 已知$ n\in \textbf{N}^+ $，在$ (2+\sqrt{x})^n $的二项展开式中，
有理项($x$的指数为正整数的项)的系数之和是29525，则$ n $是多少？(允许使用计算器)\\
\textbf{解}\ $ (2+\sqrt{x})^n $展开的系数与$ (2+x)^n $一样，令
\begin{align*}
    (2+x)^n=a_0+a_1x+a_2x^2+\cdots a_nx^n 
\end{align*}
上式中，$ x $的偶数次项对应$ (2+\sqrt{x})^n $的二项展开式中的有理项，
在上式中分别令$ x=1,-1 $，有
\begin{align*}
    (2+1)^n =&\ a_0+a_1+a_2+\cdots + a_n  \\
    (2-1)^n =&\ a_0-a_1+a_2-\cdots +(-1)^na_n 
\end{align*}
两式相加，
\begin{align*}
    3^n+1=2(a_0+a_2+a_4+\cdots )=2\times 29525
\end{align*}
所以，$ n=10 $. 

\item 设$ (3+2x)^{20}=a_0+a_1(x-1)+a_2(x-1)^2+\cdots+a_{20}(x-1)^{20} $. \\
(1) 求$ a_{15} $；\\
(2) 求$ a_{1}+a_{3}+a_{5}+\cdots+a_{19} $；\\
(3) 求$ (a_{0}+a_{2}+a_{4}+\cdots+a_{20})^2-
(a_{1}+a_{3}+a_{5}+\cdots+a_{19})^2 $. \\
\textbf{解}\ (1) \textbf{方法一}
\begin{align*}
    (3+2x)^{20}=[5+2(x-1)]^{20}=
    \sum_{k=0}^{20}C_{20}^{k}\cdot 5^k[2(x-1)]^{20-k}
\end{align*}
令$ k=5 $，得$ a_{15}=C_{20}^5 \cdot 5^5\cdot 2^{15} $. \\
\textbf{方法二}\ 左右两侧对$ x $求导15次(或者说求15阶导数)，
\begin{align*}
    \dfrac{20!}{5!} \cdot 2^{15}(3+2x)^5= 15!a_{15}+
    \dfrac{16!}{2!}a_{16}(x-1)+\cdots+\dfrac{20!}{5!}a_{20}(x-1)^5
\end{align*}
令$ x=1 $，得$ \dfrac{20!}{5!} \cdot 2^{15}\cdot 5^5=15!a_{15} $，
所以，$ a_{15}=\dfrac{20!}{5!\cdot 15!}\cdot 2^{15}\cdot 5^5=
C_{20}^5 \cdot 5^5\cdot 2^{15} $. \\
\textbf{注}：$ a_0,a_1,a_2,\cdots $实际上就是函数$ f(x)=(3+2x)^{20} $
在$ x=1 $处的泰勒级数的系数。\\
(2) 令$ x=2 $可得：
\begin{gather*} 
    5^{20}=a_0+a_1+a_2+a_3+\cdots+a_{20}  \tag*{\ding{172}}
\end{gather*}
令$ x=0 $可得：
\begin{gather*}
    3^{20}=a_0-a_1+a_2-a_3+\cdots+a_{20}  \tag*{\ding{173}}
\end{gather*}
用\ding{172}式减去\ding{173}式，
\begin{gather*}
    5^{20}-3^{20}=2(a_{1}+a_{3}+a_{5}+\cdots+a_{19}) \\
    \dfrac{1}{2}(5^{20}-3^{20})=a_{1}+a_{3}+a_{5}+\cdots+a_{19}
\end{gather*}
(3) 利用平方差公式，再用\ding{172}式乘上\ding{173}式，
\begin{align*}
    &\ (a_{0}+a_{2}+a_{4}+\cdots+a_{20})^2-
    (a_{1}+a_{3}+a_{5}+\cdots+a_{19})^2 \\
    =&\ (a_0+a_1+a_2+a_3+\cdots+a_{20})\cdot 
    (a_0-a_1+a_2-a_3+\cdots+a_{20}) =15^{20}
\end{align*}

\item 给定$ 1,2,\cdots ,10 $共10个正整数。\\
(1) 从所给的10个数中任取$ k(k=2,3,\cdots,10) $个不同的数相乘，
求所有可能的乘积之和；\\
(2) 从所给的10个数中任取偶数个不同的数(即$ 2,4,\cdots,10 $个)相乘，
求所有可能的乘积之和。\\
\textbf{解}\ (1) 令$ f(x)=(x+1)(x+2)\cdots (x+10)=x^{10}+a_9x^9+\cdots 
+a_1x+a_0 $.\\
取出两个数相乘，相当于从$ (x+1)(x+2)\cdots (x+10) $的10个括号中的8个括号取$ x $，
剩余两个括号取常数，所以，$ 1\times 2+1\times3+\cdots+9\times 10=a_8 $；\\
类似地，取出$ k $个数相乘，所有乘积之和为$ a_{10-k} $，于是
所有可能的乘积之和为
\begin{gather*}
    a_8+a_7+\cdots+a_1+a_0=f(1)-1-a_9=11!-1-(1+2+3+\cdots+10)=11!-56
\end{gather*}
(2) 
\begin{align*}
    f(1) = 11!&=1+a_9+a_8+a_7+\cdots+a_2+a_1+a_0 \\
    f(-1)=0   &=1-a_9+a_8-a_7+\cdots +a_2-a_1+a_0 \\
    f(1)+f(-1)&=2(1+a_8+a_6+a_4+a_2+a_0) 
\end{align*}
所有偶数个数的乘积之和为
\begin{align*}
    a_8+a_6+a_4+a_2+a_0=\frac{1}{2}\left[f(1)+f(-1)\right]-1=
    \frac{1}{2}\cdot 11!-1
\end{align*}

%\item $ ^* $集合$ \{1,2,3,\cdots,1000\} $的所有子集中，总共有多少个子集满足
%子集中的所有数字之和能被5整除？(此处认为空集的所有数字之和是0，也能被5整除。)\\
%\textbf{解}\ 让我们先考虑一个更简单的集合：$ \{1,2,3,4,5\} $，
%所有数字之和能被5整除的子集有：
%\begin{gather*}
%    \varnothing,\q \underbrace{\{5\},\{1,4\},\{2,3\}}_{\text{总和为}5},
%    \q \underbrace{\{1,4,5\},\{2,3,5\},\{1,2,3,4\}}_{\text{总和为}10},
%    \q \underbrace{\{1,2,3,4,5\}}_{\text{总和为}15}
%\end{gather*}
%一共8个子集。考虑多项式$ f(x)=(1+x)(1+x^2)(1+x^3)(1+x^4)(1+x^5) $，
%将它展开，
%\begin{align*}
%    f(x)=&\ 1+x+x^2+2x^3+2x^4+3x^5+3x^6+3x^7+3x^8+3x^9+\\
%    &\ 3x^{10}+2x^{11}+2x^{12}+x^{13}+x^{14}+x^{15}
%\end{align*}
%考虑展开式中的$ x^5 $，有哪些方式可以产生它呢？有以下三种方式：
%
%\ding{172} 从$ f(x) $的5个括号中的1个括号内选出$ x^5 $，
%剩余4个括号内选出1；
%
%\ding{173} 从$ f(x) $的5个括号中的2个括号内选出$ x $和$ x^4 $，
%剩余3个括号内选出1；
%
%\ding{174} 从$ f(x) $的5个括号中的2个括号内选出$ x^2 $和$ x^3 $，
%剩余3个括号内选出1；\\
%其实，这三种选取方式正好对应子集$ \{5\},\{1,4\},\{2,3\} $，展开式中$ x^5 $
%的系数3就是选取方法数，或者说是数字之和为5的子集个数。类似地，展开式中$ x^{10} $的系数3代表$ \{1,4,5\},\{2,3,5\},\{1,2,3,4\} $这3个子集的数字之和都是10.
%所以，符合题意的子集总数就是$ x^0,x^5,x^{10},x^{15} $的系数之和，
%$ 1+3+3+1=8 $. 
%
%现在将这个方法推广到更大的集合中，令$ F(x)=(1+x)(1+x^2)\cdots(1+x^{1000}) $，将它展开
%\begin{gather*}
%    F(x)=a_0+a_1x+a_2x^2+\cdots+a_nx^n
%\end{gather*}
%其中，$ a_0=1,\  n=\dfrac{1000\times 1001}{2}=500500 $，
%在没有计算机的情况下该如何计算$ a_0+a_5+a_{10}+a_{15}+\cdots+a_n $呢？
%前面有好几个例题计算了某些展开式的奇数项之和与偶数项之和，方法是令
%$ x=\pm 1 $，本题显然不能令$ x=\pm 1 $了。令$ x=\pm 1 $的方法的本质是
%数列$ \{(-1)^n\} $的周期是2，而本题需要一个周期为5的数列，怎么办呢？
%读者能否联想到1的5次单位根呢？即数列$ \{(\e^{2\pi\i/5})^n\} $的周期是5.
%\begin{align*}
%    F(1)&=2^{1000}\\ &=a_0+a_1+a_2+\cdots+a_n \\
%    F(\e^{2\pi\i/5})&=(1+\e^{2\pi\i/5})(1+\e^{4\pi\i/5})\cdots
%    (1+\e^{2000\pi\i/5})\\ &=a_0+a_1\e^{2\pi\i/5}+a_2\e^{4\pi\i/5}
%    +\cdots+a_n\e^{2n\pi\i/5} \\
%    F(\e^{4\pi\i/5})&=(1+\e^{4\pi\i/5})(1+\e^{8\pi\i/5})\cdots
%    (1+\e^{4000\pi\i/5})\\ &=a_0+a_1\e^{4\pi\i/5}+a_2\e^{8\pi\i/5}
%    +\cdots+a_n\e^{4n\pi\i/5} \\
%    F(\e^{6\pi\i/5})&=(1+\e^{6\pi\i/5})(1+\e^{12\pi\i/5})\cdots
%    (1+\e^{6000\pi\i/5})\\ &=a_0+a_1\e^{6\pi\i/5}+a_2\e^{12\pi\i/5}
%    +\cdots+a_n\e^{6n\pi\i/5} \\
%    F(\e^{8\pi\i/5})&=(1+\e^{8\pi\i/5})(1+\e^{16\pi\i/5})\cdots
%    (1+\e^{8000\pi\i/5})\\ &=a_0+a_1\e^{8\pi\i/5}+a_2\e^{16\pi\i/5}
%    +\cdots+a_n\e^{8n\pi\i/5} 
%\end{align*}
%$ z^5-1=(z-1)(z-\e^{2\pi\i/5})(z-\e^{4\pi\i/5})(z-\e^{6\pi\i/5})
%(z-\e^{8\pi\i/5}) $，令$ z=-1 $得：
%\begin{align*}
%    & (1+\e^{2\pi\i/5})(1+\e^{4\pi\i/5})(1+\e^{6\pi\i/5})
%    (1+\e^{8\pi\i/5})=1 \\
%    & (1+\e^{2\pi\i/5})(1+\e^{4\pi\i/5})(1+\e^{6\pi\i/5})
%    (1+\e^{8\pi\i/5})(1+\e^{10\pi\i/5})=2
%\end{align*}
%而且，对任意$ k=1,2,3,4 $，都有：
%\begin{align*}
%    &\ (1+\e^{2k\pi\i/5})(1+\e^{4k\pi\i/5})(1+\e^{6k\pi\i/5})
%    (1+\e^{8k\pi\i/5})(1+\e^{10k\pi\i/5}) \\
%    =&\ (1+\e^{2\pi\i/5})(1+\e^{4\pi\i/5})(1+\e^{6\pi\i/5})
%    (1+\e^{8\pi\i/5})(1+\e^{10\pi\i/5})=2
%\end{align*}
%对任意$ k=1,2,\cdots,1000 $，都有：
%\begin{gather*}
%    1+\e^{2k\pi\i/5}+\e^{4k\pi\i/5}+\e^{6k\pi\i/5}
%    +\e^{8k\pi\i/5}=0
%\end{gather*}
%所以，
%\begin{align*}
%    &\ F(\e^{2\pi\i/5})=F(\e^{4\pi\i/5})=F(\e^{6\pi\i/5})
%    =F(\e^{8\pi\i/5}) \\
%    =&\ [(1+\e^{2k\pi\i/5})(1+\e^{4k\pi\i/5})(1+\e^{6k\pi\i/5})
%    (1+\e^{8k\pi\i/5})(1+\e^{10k\pi\i/5})]^{1000/5} \\
%    =&\ 2^{1000/5}=2^{200}
%\end{align*}
%\begin{align*}
%    &\ F(1)+F(\e^{2\pi\i/5})+F(\e^{4\pi\i/5})+F(\e^{6\pi\i/5}) 
%    +F(\e^{8\pi\i/5}) \\ =&\ 2^{1000}+4\cdot 2^{200} \\
%    =&\ 5(a_0+a_5+a_{10}+a_{15}+\cdots +a_n) 
%\end{align*}
%\begin{gather*}
%    a_0+a_5+a_{10}+a_{15}+\cdots +a_n=
%    \dfrac{1}{5}(2^{1000}+4\cdot 2^{200})
%\end{gather*}
%所以，满足题意的子集总个数为$ \dfrac{1}{5}(2^{1000}+4\cdot 2^{200}) $.
%如果把1000改成5，也可以用以上公式检验一下最初分析的$ \{1,2,3,4,5\} $
%这个简单的集合，$ \dfrac{1}{5}(2^{5}+4\cdot 2^{5/5})=8 $. 

\item 现有1元、5元、10元、20元的纸币若干(每一种面额的纸币数量都足够多)，
要恰好支付34元，共有多少种方法？ \\
\textbf{方法一}\ 对于此类货币组合问题，总体思路是确定最大面额的货币所
允许的最大数量，然后从最大数量开始递减到0. 当最大面额货币数量固定后，
对次最大的面额执行相同的步骤：从最大数量递减到0. 依次类推。\\
\ding{172} 使用1张20元，然后只需凑14元，
有$ 10+1\times 4 $，$ 5\times 2+
1\times 4 $，$ 5+1\times 9 $，$ 1\times 14 $共4种方法。
(先是10元的数量从1递减到0，然后是5元的数量从2递减到0.)\\
\ding{173} 不使用20元，至少使用2张10元，则方法数与(1)相同，也是4种。\\
\ding{174} 不使用20元，使用1张10元，有$ 10+5\times 4+1\times 4 $，
$ 10+5\times 3+1\times 9 $，$ 10+5\times 2+1\times 14 $，
$ 10+5\times 1+1\times 19 $，$ 10+1\times 24 $，
(实际上就是5元的数量从4递减到0)，共5种。\\
\ding{175} 不使用20元，也不使用10元，那么5元的数量从6递减到0，共7种。\\
综合以上，一共有$ 4+4+5+7=20 $种方法。\\
\textbf{方法二}$ ^* $\ 生成函数法(正整数分拆问题的通法
\footnote{参见许胤龙、孙淑玲编著的《组合数学引论》。})，
\begin{gather*}
    \dfrac{1}{(1-x^1)(1-x^5)(1-x^{10})(1-x^{20})}=\\
(1+x+x^2+x^3+\cdots)\cdot(1+x^5+x^{10}+x^{15}+\cdots)\cdot\\
(1+x^{10}+x^{20}+x^{30}+\cdots)\cdot(1+x^{20}+x^{40}+x^{60}+\cdots)=\\
1+x+x^{2}+x^{3}+x^{4}+2x^{5}+2x^{6}+2x^{7}+2x^{8}+2x^{9}+4x^{10}+4x^{11}+4x^{12}+4x^{13}\\
+4x^{14}+6x^{15}+6x^{16}+6x^{17}+6x^{18}+6x^{19}+10x^{20}+10x^{21}+10x^{22}+10x^{23}+10x^{24}\\
+14x^{25}+14x^{26}+14x^{27}+14x^{28}+14x^{29}+20x^{30}+20x^{31}+20x^{32}+20x^{33}+20x^{34}+\cdots
\end{gather*}
凑出$ n $元的方法数等于$ x^n $的系数，对本题而言就是
$ x^{34} $的系数20. 请读者再从中随意挑选几项，
用方法一或者其它方法进行计算，然后与上面的系数进行比对。
上面大量的系数是利用MATLAB求泰勒级数算出的，语法如下：
\begin{lstlisting}
syms x
f(x)=1/(1-x^1)/(1-x^5)/(1-x^10)/(1-x^20);
taylor(f(x),x,0,'order',35)    
\end{lstlisting} 

\item 将$ \dfrac{1}{12} $写成两个分子为1、分母为正整数的分数之和，
即$ \dfrac{1}{12}=\dfrac{1}{a}+\dfrac{1}{b},\ a,b\in\textbf{N}^+ $，
总共有多少种不同的写法？
(不考虑$ a,b $的顺序)。\\
\textbf{方法一}\ 12的因数有$ 1,2,3,4,6,12 $，从这6个因数每次取2个(可以重复)，不同比例的组合有$ (1,1) $,$ (1,2) $,$ (1,3) $,$ (1,4) $,$ (1,6) $,$ (1,12) $,$ (2,3) $,$ (3,4) $，总共8种。
\begin{align*}
    & \dfrac{1+1}{12\times(1+1)}=\dfrac{1}{24}+\dfrac{1}{24} 
    & \dfrac{1+2}{12\times(1+2)}=\dfrac{1}{36}+\dfrac{2}{36}=\dfrac{1}{36}+\dfrac{1}{18}\\
    & \dfrac{1+3}{12\times(1+3)}=\dfrac{1}{48}+\dfrac{3}{48}=\dfrac{1}{48}+\dfrac{1}{16} 
    & \dfrac{1+4}{12\times(1+4)}=\dfrac{1}{60}+\dfrac{4}{60}=\dfrac{1}{60}+\dfrac{1}{15} \\
    & \dfrac{1+6}{12\times(1+6)}=\dfrac{1}{84}+\dfrac{6}{84}=\dfrac{1}{84}+\dfrac{1}{14} 
    & \dfrac{1+12}{12\times(1+12)}=\dfrac{1}{156}+\dfrac{12}{156}=
    \dfrac{1}{156}+\dfrac{1}{13} \\
    & \dfrac{2+3}{12\times(2+3)}=\dfrac{2}{60}+\dfrac{3}{60}=\dfrac{1}{30}+\dfrac{1}{20} 
    & \dfrac{3+4}{12\times(3+4)}=\dfrac{3}{84}+\dfrac{4}{84}=\dfrac{1}{28}+\dfrac{1}{21} 
\end{align*}
\textbf{方法二}\ $ \dfrac{1}{n}=\dfrac{1}{a}+\dfrac{1}{b}=\dfrac{a+b}{ab},\ ab=n(a+b) $，
于是，
\begin{gather*}
    ab-n(a+b)+n^2=(a-n)(b-n)=n^2 \\
    (a-12)(b-12)=12^2=144=1\times144=2\times72=3\times48=4\times36=\\
    6\times24= 8\times18=9\times16=12\times12
\end{gather*}
所以，$ (a-12,b-12) $可以等于$ (1,144)$, $(2,72)$, $(3,48)$, $(4,36)$, $(6,24)$, 
$(8,18)$, $(9,16) $, $(12,12)$, $ a,b $的取值同方法一，总共8种。\\
\\
对于任意大于1的整数$ n $，一定存在两个\underline{不相等}的正整数
$ a,b $，满足$ \dfrac{1}{n}=\dfrac{1}{a}+\dfrac{1}{b} $，
请问该如何构造$ a,b $？
(答案就隐藏在上面的方法一中，也放在了本页的脚注中。
\footnote{$ \dfrac{1}{n}=\dfrac{n+1}{n(n+1)}=
   \dfrac{1}{n+1}+\dfrac{1}{n(n+1)}=\dfrac{1}{a}+\dfrac{1}{b}$} )

\item $ ^* $ 已知$ a,b $为正实数，且满足
$ \dfrac{1}{a}+\dfrac{1}{b}=1 $，求证：
$ (a+b)^n-a^n-b^n\geq 2^{2n}-2^{n+1} $，
其中$ n \in \textbf{N}^+ $. \\
\textbf{方法一}\ $ ab=a+b=(a+b)\left(\dfrac{1}{a}+
\dfrac{1}{b}\right)=2+\dfrac{b}{a}+\dfrac{a}{b}\geq 4 $. 
使用归纳法：$n=1,2$时，结论显然成立，假设$n=k$时结论成立，
当$n=k+1$时，
\begin{align*}
    (a+b)^{k+1}-a^{k+1}-b^{k+1}
    =&\  (a+b)[(a+b)^k-a^k-b^k]+ a^kb+ab^k \\ 
    \geq &\ 4(2^{2k}-2^{k+1})+2\sqrt{a^kb\cdot ab^k} \\
       = &\ 4(2^{2k}-2^{k+1})+2\sqrt{(ab)^{k+1}} \\
    \geq &\ 4(2^{2k}-2^{k+1})+2^{k+2}=2^{2(k+1)}-2^{k+2}
\end{align*}
$a=b=2$时，等号成立。\\
\textbf{方法二}\ 同样有$ab\geq 4$，倒序相加：
\begin{align*}
    S_n =&\ (a+b)^n-a^n-b^n \\
    =&\ C_n^1ab^{n-1}+C_n^2a^2b^{n-2}+\cdots +C_n^{n-1}a^{n-1}b \\
    =&\ C_n^1a^{n-1}b+C_n^2a^{n-2}b^2+\cdots +C_n^{n-1}ab^{n-1} \\  
    2S_n=&\ C_n^1(ab^{n-1}+a^{n-1}b)+C_n^2(a^2b^{n-2}+a^{n-2}b^2)+\cdots 
    +C_n^{n-1}(a^{n-1}b+ab^{n-1}) \\ 
    \geq &\ (C_n^1+C_n^2+\cdots +C_n^{n-1}) 2\sqrt{a^nb^n}=(2^n-2)\cdot 2^{n+1}
\end{align*}
所以，$ S_n \geq 2^{2n}-2^{n+1} $. $a=b=2$时，等号成立。
%~\newpage

\end{enumerate}

\section{习题}
\begin{enumerate}[label={\textbf{\thechapter.\arabic*}},leftmargin=
    \inteval{\myenumleftmargin}pt]
    
\item 6人分乘两辆不同的车，每车最多乘4人，则不同的乘车方法有多少种？

\item 一排6个座位，3个人坐，3个空位中恰好有2个连在一起的坐法有多少种？

\item 在11名工人中，有5人只能当钳工，4人只能当车工，
另外2人能当钳工也能当车工．现从11人中选出4人当钳工，
4人当车工，共有多少种不同的选法？

\item 将一个五棱锥的每一个面染一种颜色，要求相邻两面不同色，
如果有6种不同的颜色供选用，则不同的染色方法有多少种？

\item (1) 以正方体的顶点为顶点的四面体一共有多少个？
(假设正方体是固定的，全等的四面体只要空间位置不同，
都认为是不同的四面体。) \\
(2) 正方体8个顶点可连成多少对异面直线?

\item 去掉括号并化简下列式子：\\
(1) $ \left(9t^4\right)^3+\left(3t-9t^4\right)^3+
\left(1-9t^3\right)^3 $ \\
(2) $ \left(1+6t^3\right)^3+\left(1-6t^3\right)^3+
\left(-6t^2\right)^3 $

\item 求$ \left(2x+\dfrac{3}{x}\right)^{14} $展开式中系数最大的项。

\item 完成表\ref{组合恒等式}中全部组合恒等式的证明。\\
(提示：对于$ \sum\limits_{k=r}^{n} C_k^r $，将首项$ C_r^r $换成$ C_{r+1}^{r+1} $，两者都是1；\\
$ k^2C_n^k=k(k-1)C_n^k+kC_n^k $，$ k(k-1)C_n^k=n(n-1)C_{n-2}^{k-2} $，还可以将(\ref{二项展开式两边求导})式两边求导。2008年江苏高考就考察了两边同时求导的方法。\\
$\sum\limits_{k=0}^{n} \left( C_{n}^k\right) ^2=C_{2n}^n$是
$ \sum\limits_{k=0}^{r}C_m^kC_n^{r-k}=C_{m+n}^r $在$m=n=r$时的特例，
从$m+n$件物品中选出$r$件物品，可以先从$m$件物品中选出$k$件，
再从$n$件物品中选出$r-k$件，方法数是$ C_m^kC_n^{r-k} $，$k$可以取
0到$r$，求和即可。\\
其它等式并无难度。)

\item 求证：对任意正整数$ n>1 $，有$ \dfrac{4^n}{2\sqrt{n}}<
C_{2n}^{n} < \dfrac{4^n}{\sqrt{3n+1}} $. \\
扩展：根据斯特林公式\eqref{斯特林公式指数形式}，$n!\approx \sqrt{2\pi n}
\left(\dfrac{n}{\e}\right)^n$，那么
\begin{gather*}
    \lim_{n\to+\infty}\dfrac{C_{2n}^n}{\frac{4^n}{\sqrt{n}}}  = \lim_{n\to+\infty}
    \dfrac{2n!\cdot \sqrt{n}}{(n!)^2\cdot 4^n} 
    = \lim_{n\to+\infty} \dfrac{\sqrt{2\pi \cdot 2n}\left(\dfrac{2n}{\e}
        \right)^{2n}\cdot \sqrt{n}}{\left[\sqrt{2\pi n}
        \left(\dfrac{n}{\e}\right)^n\right]^2 \cdot 4^n} = \dfrac{1}{\sqrt{\pi}}    
\end{gather*}
本题中的不等式，实际上相当于$\dfrac{1}{\sqrt{4}}<\dfrac{1}{\sqrt{\pi}}
<\dfrac{1}{\sqrt{3}}$.

\item 设$ \dfrac{1}{30}=\dfrac{1}{a}+\dfrac{1}{b},\ a,b\in\textbf{N}^+ $，
不考虑$ a,b $的顺序，总共有多少种不同的拆分方法？

\item 现有$ 0\sim 6 $共7个整数，不重复地从中选出一些数完成下列任务：\\
(1)构成4位的偶数，有多少种选法？\\
(2)构成5位数，且能被3整除，有多少种选法？\\
(3)构成6位数，从小到大排列，第100个数是多少？

\item 现有1元、2元、5元、10元的纸币若干(每一种面额的纸币数量都足够多)，
要恰好支付26元，共有多少种方法？ 

\item 数轴上有一个质点从原点出发，每次只能向正方向跳197个单位或者
向负方向跳149个单位。质点最少需要跳多少次，才能到达刻度为1的点？

\end{enumerate}


\section{习题答案}
\begin{enumerate}[label={\textbf{\thechapter.\arabic*}},leftmargin=
    \inteval{\myenumleftmargin}pt]
\item $ 2C_6^2+C_6^3=2\times 15+20=50 $.

\item \textbf{方法一}\ 先将3个人全排列，再把2个空位绑在一起，
和另一个空位向3个人之间和两端插空，
总方法数是$P_3^3 C_4^2=6\times 12 =72$.  \\
\textbf{方法二}\ 3个人随意座，有$ P_6^3=120 $种。\\
3个空位绑在一起变成一个“人”，总共4个人，有$P_4^4=24$种；\\
3个空位均不相连，然后3个人全排列，有$C_4^3P_3^3=24$种；\\
符合题意的就剩$ 120-24-24=72$.

\item 只能当钳工的5人记为甲类，只能当车工的4人记为乙类，
能当钳工也能当车工的2人记为丙类，\\
(1) 从丙类中选出2人当钳工，甲类中选出2人当钳工，乙类中选出4人当车工，有$ C_5^2=10 $种；\\
(2) 从丙类中选出1人当钳工，甲类中选出3人当钳工，乙类+丙类中选出4人当车工，有$ C_2^1C_5^3C_5^4=100 $种；\\
(3) 从丙类中选出0人当钳工，甲类中选出4人当钳工，乙类+丙类中选出4人当车工，有$ C_5^4C_6^4=75 $种；\\
一共$10+100+75=185$种。

\item 先把底面涂色，有6种选择。然后用剩余的5种颜色对5个侧面进行环形染色，
根据\eqref{环形染色-an统一表达式}式，有$(5-1)^5+(-1)^5(5-1)=1020$种方法，
于是共有$6\times 1020=6120$种染色方法。

\item (1) 8个顶点任选4个，有$C_8^4=70$种，考虑四点共面的情形：\\
(一) 四点位于正方体的同一个面上，共6种；\\
(二) 四点位于相对的面上相互平行的对角线上，相对的面有3组，
每组两条对角线，共6种；\\
最终结果为$70-6-6=58$种。\\
(2) 前一问中的每个四面体包含3对异面直线，那么能不能直接把前一问
的结果乘以3呢？是可以的，因为一对异面的线段就能唯一确定一个四面体，
一个四面体包含3对异面线段，这3对异面线段都不会出现在其它四面体中，
所以，$3\times 58=174$
这个结果并不会包含任何重复计数，就是正确结果。


\item (1) $ \left(9t^4\right)^3+\left(3t-9t^4\right)^3+
\left(1-9t^3\right)^3=1 $ \\
(2) $ \left(1+6t^3\right)^3+\left(1-6t^3\right)^3+
\left(-6t^2\right)^3=2 $ \\
这两个恒等式意味着，方程$a^3+b^3+c^3=1(\text{或}2)$存在无穷多组
整数解。

% plot(fliplr(coeffs(expand((2*x+3)^14))),'k.','markersize',20);
% axis([0 14 -10^8 3.6*10^9]);grid on
\item 根据\eqref{二项式系数最大值不等式组的解}式，
$ 8=\dfrac{3\cdot 14-2}{5}\leq m\leq \dfrac{3\cdot 14 +3}{5}=9 $，
所以系数最大的有两项：$ C_{14}^{8}(2x)^6(3)^8=1260971712x^{6},\ 
C_{14}^{9}(2x)^5(3)^9=1260971712x^{5} $. 系数图像如下：
\begin{figure}[h]
    \centering
    \includegraphics[width=0.4\linewidth]{二项式系数最大2}
\end{figure}

\item 略

\item 当$ n=2 $ 时，$ \dfrac{4^2}{2\sqrt{2}}=4\sqrt{2}<
C_4^2=6<\dfrac{4^2}{\sqrt{7}}=\sqrt{\dfrac{256}{7}} $\q 
$ (36\times 7=252<256) $. \\
$ \dfrac{\frac{4^{n+1}}{2\sqrt{n+1}}}
{\frac{4^{n}}{2\sqrt{n}}}=\dfrac{4\sqrt{n}}{\sqrt{n+1}} $，
$ \dfrac{C_{2n+2}^{n+1}}{C_{2n}^{n}}=
\dfrac{4(n+\frac{1}{2})}{n+1} $，
$ \dfrac{\frac{4^{n+1}}{\sqrt{3n+4}}}
{\frac{4^{n}}{\sqrt{3n+1}}}=\dfrac{4\sqrt{3n+1}}{\sqrt{3n+4}} $，
只需证明：
\begin{gather}\label{C_2n_n的不等式题目}
    \dfrac{\sqrt{n}}{\sqrt{n+1}}<\dfrac{n+\frac{1}{2}}{n+1}
    <\dfrac{\sqrt{3n+1}}{\sqrt{3n+4}}
\end{gather}
左半部分的不等式等价于$\sqrt{n(n+1)}<n+\dfrac{1}{2}$，两边平方以后是显然的。
右半部分的不等式等价于$ \left(n+\dfrac{1}{2}\right)^2(3n+4)-
(n+1)^2\sqrt{3n+1}=-\dfrac{n}{4}<0 $. 把\eqref{C_2n_n的不等式题目}式
的分子都乘以4，再取$n-1$个这样的式子累乘即可。

\item 30的因数有$ 1,2,3,5,6,10,15,30 $，从这8个因数每次取2个，不同比例的组合有\\
$ (1,1) $,$ (1,2) $,$ (1,3) $,$ (1,5) $,$ (1,6) $,$(1,10)$,
$ (1,15) $, $(1,30)$,\\
$ (2,3) $,$(2,5)$,$(2,15)$,\\
$ (3,5) $, $(3,10)$，\\
$ (5,6) $,\\
总共14种。

\item (1) 个位为0时，有$P_6^3=120$种；\\
个位为$2,4,6$时，因为0不能出现在首位，首位有5种选择。
有$ 3\times 5 \times 5 \times 4= 300 $种；\\
一共420种。\\
(2) $0+1+2+3+4+5+6=21$，能被3整除的数，各位数字之和也能被3整除，
$ 0\sim 6 $这7个数的和为21，恰好能被3整除，从中选5个数，
意味着剩余2个数字之和也要能被3整除，有如下可能
$ 0+3,\ 0+6,\ 1+2,\ 1+5,\ 2+4,\ 3+6,\ 4+5 $.\\
剩余$0+3,\ 0+6$时，有$2P_5^5=240$种；\\
剩余$1+2,\ 1+5,\ 2+4,\ 3+6,\ 4+5 $时，有$5\times4 P_4^4=480$种；\\
一共720种。\\
(3) 可构成的最小的6位数是$ 102345 $，以10开头的6位数，一共有
$P_5^4=120$个，这120个数中，最大的数为$106543$，从大到小的第21个，
就是从小到大的第100个。以106开头的6位数，一共有
$P_4^3=24 $种，这24个数从小到大为$106234,\ 106235,
\ 106243,\ 106245 $，第4个数106245便是最终结果。

\item \textbf{方法一}\ 
(1)使用2张10元，有$ 5+1 $，$ 2\times 3 $，
$ 2\times 2+1\times 2 $，$ 2\times 1+1\times 4 $，
$ 1\times 6 $，共5种。\\
(2)使用1张10元，至少2张5元，方法数与(1)相同，共5种。\\
(3)使用1张10元，若使用1张5元，2元的数量从5递减到0，共6种；
若使用0张5元，2元的数量从8递减到0，共9种；\\
(4)不使用10元，5张5元，共1种；4张5元，2元的数量从3递减到0，共4种；
3张5元，2元的数量从5递减到0，共6种；2张5元，2元的数量从8递减到0，共9种；
1张5元，2元的数量从10递减到0，共11种；0张5元，2元的数量从13递减到0，共14种；\\
综合以上，一共有$ 5+5+6+9+1+4+6+9+11+14=70 $种方法。\\
\textbf{方法二}$ ^* $\ 生成函数法，
\begin{gather*}
    \dfrac{1}{(1-x^1)(1-x^2)(1-x^{5})(1-x^{10})}=\\
    1+x+2x^{2}+2x^{3}+3x^{4}+4x^{5}+5x^{6}+6x^{7}+7x^{8}+8x^{9}+11x^{10}+12x^{11}+15x^{12}\\ +16x^{13}+19x^{14}+22x^{15}+25x^{16}+28x^{17}+31x^{18}+34x^{19}+40x^{20}+43x^{21}+49x^{22}\\
    +52x^{23}+58x^{24}+64x^{25}+70x^{26}+\cdots
\end{gather*}
凑出26元的方法数就等于$ x^{26} $的系数70. 

\item 假设正方向跳动了$x$次，负方向跳动了$y$次，那么
$ 197x-149y=1 $，
\begin{align*}
    197\div 149 &=1 \cdots\cdots 48 \\
    149\div  48 &=3 \cdots\cdots 5  \\
    48\div   5 &=9 \cdots\cdots 3 \\
    5\div   3 &=1 \cdots\cdots 2 \\
    3\div   2 &=1 \cdots\cdots 1 
\end{align*}
于是，
\begin{align*}
    1 &= 3-2 \\
    &= 3-(5-3) \\
    &= 3\times 2-5\\
    &= (48-5\times 9)\times 2-5\\
    &= 48\times 2-5\times 19 \\
    &= 48\times 2-(149-48\times 3)\times 19 \\
    &= 48\times 59-149\times 19 \\
    &= (197-149)\times 59-149\times 19 \\
    &= 197\times 59-149\times 78    
\end{align*}
$ 197\times(59+149n)-149\times(78+197n)=1 $，
质点最少需要跳动$59+78=137$次。
 
\end{enumerate}
\myfootnote{\CopyrightStatementChap}
% {\footnotesize (可在以下空白区域自行增补知识点。)}  
\cleardoublepage

%~\newpage
%~\newpage
%------------------------------------------
